package main.java.person.fjsp.algorithm.ts;

import main.java.person.fjsp.algorithm.ts.entity.DisjunctiveGraph;
import main.java.person.fjsp.algorithm.ts.utils.TSUtils;
import main.java.person.fjsp.common.entity.DataManager;

import java.util.*;

/**
 * 禁忌搜索
 */
public class TSSolver {

    /**
     * 禁忌长度
     */
    private int tabuLen;
    /**
     * 迭代次数
     */
    private int epochs;
    /**
     * 局部搜索次数
     */
    private int localSearchNum;
    /**
     * 能忍受无更优解的最大迭代次数
     */
    private int maxNotBetterNum;

    private TSUtils tsUtils=new TSUtils();

    public TSSolver(int tabuLen, int epochs, int localSearchNum, int maxNotBetterNum) {
        this.tabuLen = tabuLen;
        this.epochs = epochs;
        this.localSearchNum = localSearchNum;
        this.maxNotBetterNum=maxNotBetterNum;
    }

    /**
     * 禁忌搜索算法主入口
     * @param graph 析取图
     * @return 禁忌搜索得到的最优解
     */
    public DisjunctiveGraph solve(DisjunctiveGraph graph, DataManager dataManager){
        //最优解
        DisjunctiveGraph bestSolution=graph;
        //当前解
        DisjunctiveGraph curSolution=graph;
        //禁忌表
        LinkedList<Integer> tabuList=new LinkedList<>();
        //禁忌表的哈希集合，用来辅助查找
        HashSet<Integer> tabuSet = new HashSet<>();
        int notBetterNum=0;
        for (int i = 0; i < epochs; i++) {

            //局部搜索得到局部最优解，赋给当前解
            curSolution = localSearch(curSolution, dataManager, tabuSet);
            if(null!=curSolution){
                //更新禁忌表
                updateTabuList(tabuList,tabuSet,Arrays.hashCode(curSolution.getInsertInfo()));
                if(bestSolution.getMakespan()>curSolution.getMakespan()){
                    notBetterNum=0;
                    bestSolution=curSolution;
//                    System.out.println("-------- epoch:"+i+" ---------");
//                    System.out.println("更新："+bestSolution.getMakespan());
                }else {
                    notBetterNum++;
                }
                if(notBetterNum>=maxNotBetterNum){
                    break;
                }
            }
        }
        return bestSolution;
    }

    /**
     * 进行局部邻域搜索
     * @param solution 要进行邻域扰动的解（邻域动作不会影响到solution）
     * @return 局部邻域搜索之后的最优解
     */
    private DisjunctiveGraph localSearch(DisjunctiveGraph solution,DataManager dataManager,HashSet<Integer> tabuSet){
        //这里一定是选出solution的邻居候选解的最优解，而不是选出一个比solution更优的解（这样跳不出局部最优）
        DisjunctiveGraph localBest=null;
        for (int i = 0; i < localSearchNum; i++) {
            DisjunctiveGraph curLocal = solution.clone();
            int[] insertInfo = tsUtils.getInsertInfo(curLocal, dataManager);
            //该插入操作被禁忌，不需要插入
            if(tabuSet.contains(Arrays.hashCode(insertInfo))){
                continue;
            }
            //进行k-insertion
            tsUtils.kInsertion(curLocal, dataManager, insertInfo);
            if(localBest==null||curLocal.getMakespan()<localBest.getMakespan()){
                localBest=curLocal;
            }
        }
        //没有找到更优解，返回原解
        return localBest;
    }

    /**
     * 更新禁忌表
     * @param tabuList 禁忌表
     * @param tabuSet 禁忌表的哈希集合
     * @param info 要禁忌的插入操作
     */
    private void updateTabuList(LinkedList<Integer> tabuList,HashSet<Integer> tabuSet,int info){
        if(tabuList.size()>=tabuLen){
            tabuSet.remove(tabuList.get(0));
            tabuList.removeFirst();
        }
        tabuList.add(info);
        tabuSet.add(info);

    }

}
